/**
 *   This file is part of Graph-Tool.
 *
 *   Graph-Tool is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Graph-Tool is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Graph-Tool.  If not, see <http://www.gnu.org/licenses/>.
 */
package graphtool.graphs;

import graphtool.math.matrices.IndexException;

import java.util.Collection;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;

/**
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 *
 */
public class DirectedGraph<V, E> extends BaseGraph<V, E>
{
  
  Hashtable<E, Pair<V,V> > _edgeTrack;
  
  public DirectedGraph()
  {
    _edgeTrack = new Hashtable<E, Pair<V, V>>(); 
  }
  
  /**
   * @Override
   */
  public void addEdge( E e, V srcV, V targetV ) throws GraphPropertyException
  {
    super.addEdge( e, srcV, targetV );
    
    _edgeTrack.put( e, new Pair<V,V>( srcV, targetV ));
  }
  
  /**
   * @Override
   */
  public void removeEdge( E e, V src, V target ) throws GraphPropertyException
  {
    super.removeEdge( e, src, target );
    
    _edgeTrack.remove( e );
  }
  
  /**
   * Returns the collection of predecessors of the given node.
   * 
   * @param v
   * @return
   */
  public Collection<V> getPredecessors( V v )
  {
    Collection<E> incidents = this.incidents( v );
    
    Iterator<E> iter = incidents.iterator();
    
    Collection<V> predecessors = new Vector<V>();
    
    while( iter.hasNext() )
    {
      E e = iter.next();
      
      Pair<V,V> p = _edgeTrack.get( e );
      
      if( p.getValue().equals( v ))
      {
        predecessors.add( p.getKey());
      }
    }
    
    return predecessors;
  }
  
  /**
   * Returns a collection of successors of the specified vertex
   * 
   * @param v
   * @return
   */
  public Collection<V> getSuccessors( V v )
  {
    Collection<E> incidents = this.incidents( v );
    
    Iterator<E> iter = incidents.iterator();
    
    Collection<V> successors = new Vector<V>();
    
    while( iter.hasNext() )
    {
      E e = iter.next();
      
      Pair<V,V> p = _edgeTrack.get( e );
      
      if( p.getKey().equals( v ))
      {
        successors.add( p.getValue());
      }
    }
    
    return successors;
  }
  
  /**
   * Returns the source of the specified edge
   * 
   * @param e
   * @return
   */
  public V getSource( E e )
  {
    return _edgeTrack.get( e ).getKey();
  }
  
  /**
   * Returns the destination of the specified edge
   * 
   * @param e
   * @return
   */
  public V getTarget( E e )
  {
    return _edgeTrack.get( e ).getValue();
  }
  
  /**
   * Returns the endpoints of the edge
   * @param e
   * @return
   */
  public Pair<V,V> getNodes( E e )
  {
    return _edgeTrack.get( e );
  }
  
  public E findEdge( V v1, V v2 ) throws IndexException
  {
    int row = _vertices.indexOf( v1 );
    int row2 = _vertices.indexOf( v2 );
    
    for( int i = 0; i < _incidence.columns(); i++ )
    {
      double[] column = _incidence.getColumn( i );
      
      if( column[ row ] > 0  && column[ row2 ] > 0 )
        return _edges.get( i );
    }
    
    return null;
  }
  
  public String toString()
  {
    StringBuffer buffer = new StringBuffer();

    buffer.append( "------------ Directed Gaph --------------\n" );
    buffer.append( "Count of edges: " + _edges.size() + "\n" );
    buffer.append( "Count of vertices: " + _vertices.size() + "\n" );

    buffer.append( "Adjacence:\n" + _adjacency );
    buffer.append( "Incidence:\n" + _incidence );

    Iterator<E> eIter = _edges.iterator();

    while( eIter.hasNext() )
    {
      E e = eIter.next();

      Pair<V, V> p = this.getEndpoints( e );

      buffer.append( "V: " + p.getKey() + " E: " + e + " V: " + p.getValue() + "\n" );
    }
    return buffer.toString();
  }
}
